图的深度优先遍历DFS(JAVA)

您所在的位置：网站首页 › java 无向图 › 图的深度优先遍历DFS(JAVA)

图的深度优先遍历DFS(JAVA)

2023-09-27 00:38| 来源: 网络整理| 查看: 265

图的深度优先遍历算法在此介绍图的基本算法之一的深度优先遍历(DFS)算法广度优先搜索(BFS). 什么是DFS

图是由节点(Node)和路径(Route)组成的一种数据结构，用于反应各节点间的关系。我们一般会使用这种数据结构来统计节点间的关系。比如某个节点是否和其他所有节点有关联(不一定是直接关联)。这时，我们就需要根据图中的路径判断当前节点是否能够通过某条路径关联到其他所有的节点。对于这种问题，通常会使用深度优先遍历(DFS)和广度优先遍历(BFS)两种遍历方式来解决。

深度优先遍历(DFS)指的是，从指定节点开始，找到一条路径一直向下搜索，直到搜索到的当前节点无法找到新的搜索路径(当前节点直接关联的节点均已搜索过)，则返回上一级节点继续搜索其他路径，直到所有节点均已搜索到或所有路径均已搜索到。(说的通俗一点就是先一条路走到黑，不撞南墙不回头。撞了南墙再回头走其他路)

循序渐进

有如下有向图，我们的目标是统计判断从节点A出发是否能走到其他所有的节点

在这里插入图片描述

首先构造图类的数据结构； /** - 数据结构 -- 图 - 包含节点和路径 */ public class Graph { /** * 构造方法 * @param routes 路径 */ public Graph(List routes){ if(this.rotes == null){ this.rotes = new ArrayList(); } if(this.nodes == null){ this.nodes = new HashSet(); } for(Route route : routes){ this.nodes.add(route.getFrom()); this.nodes.add(route.getTo()); this.rotes.add(route); } } /** * 节点集合 */ private Set nodes; public Set getNodes() { return nodes; } /** * 路径集合 */ private List rotes; public List getRotes() { return rotes; } } /** - 路径(有向图) */ public class Route { /** * 构造方法 * @param from 开始节点 * @param to 目标节点 */ public Route(String from, String to){ this.from = from; this.to = to; } /** * 开始节点 */ private String from; public String getFrom() { return from; } /** * 目标节点 */ private String to; public String getTo() { return to; } } 构造题目中图的对象； Graph graph = new Graph(new ArrayList(){{ add(new Route("A", "B")); add(new Route("A", "C")); add(new Route("C", "B")); add(new Route("B", "E")); add(new Route("C", "D")); add(new Route("D", "F")); add(new Route("E", "F")); add(new Route("F", "G")); }}); 根据上述介绍，首先需要找到从A出发的一条路径； Route route = null; for(Route r : graph.getRotes()){ if(r.getFrom().equals("A")){ route = r; break; } } 获取找到的路径的目标节点，从该节点出发继续搜索寻找路径； for(Route r : graph.getRotes()){ if(r.getFrom().equals(route.getTo())){ route = r; break; } } 这里，我们发现每次寻找路径的处理逻辑是一致的，所以可以使用递归进行重构 public void DFS(String node, Graph graph){ Route route = null; for(Route r : graph.getRotes()){ if(r.getFrom().equals(node)){ route = r; break; } } if(route == null) return; DFS(route.getTo(), graph); }

搜索完了这条路径(撞到南墙)，可以判断从A可以到达B E F G，接下来需要回到上一级节点，再重新搜索其他路径。

这时发现根据现在的代码逻辑，无法获取上级节点的其他路径了。这是由于之前找到了一条路径后就不继续找了，等我们回头再想找的时候，无法判断那些路径我们找过那些没有找过。知道了原因，就改成找到一条路径后不停止，将这条路径搜索完后接着找下一条路径。也就是将递归放到循环里面。

public void DFS(String node, Graph graph){ Route route = null; for(Route r : graph.getRotes()){ if(r.getFrom().equals(node)){ route = r; DFS(route.getTo(), graph); } } } 发现变量route也不需要定义了，优化一下。 public void DFS(String node, Graph graph){ for(Route r : graph.getRotes()){ if(!r.getFrom().equals(node)) continue; DFS(r.getTo(), graph); } }

继续搜索，发现搜索到节点C的时候，找到了C到B的路径，然后又搜索到了B，第一条路径已经搜索过B的所有路径了，所以出现了重复搜索。这里就需要定义一个布尔型的列表来记录哪些节点已经搜索过，对于搜索过的节点，直接跳过。

这里由于节点有自己的名字，所以使用Map来记录。

public void DFS(String node, Graph graph, Map visited){ // 将当前节点标记为已搜索 visited.put(node, true); for(Route r : graph.getRotes()){ if(!r.getFrom().equals(node)) continue; // 如果当前节点已搜索，则跳过 if(visited.getOrDefault(route.getTo(), false)) continue; DFS(r.getTo(), graph, visited); } } 搜索正常结束了，可以判断从A可以到其他所有节点，但是作为一种搜索算法，最好是能统计出来各节点的搜索顺序，这里用一个列表来顺序统计搜索到的节点。发现这个列表其实就是统计哪些节点已经搜索过了，也就是和之前的Map是同样的功能。所以可以不要Map了。 public void DFS(String node, Graph graph, List visitedNodes){ // 记录访问的节点 visitedNodes.add(node); for(Route route : graph.getRotes()){ if(!route.getFrom().equals(node)) continue; // 节点已访问，则跳过 if(visitedNodes.contains(route.getTo())) continue; DFS(route.getTo(), graph, visitedNodes); } }

到此，DFS深度优先遍历算法完成。运行后可得到结果：A B E F G C D

进阶

不想使用递归方式进行深度优先搜索DFS的话，其实还可以使用栈来进行，代码如下：

/** * 深度优先遍历（栈） * * @param node 起始节点 * @return 遍历结果的节点顺序列表 */ public List DFS(String node){ List resultList = new ArrayList(); // 构建栈，加入其实节点 Stack stack = new Stack(); stack.add(node); while(!stack.isEmpty()){ // 将栈顶节点出栈并加入搜索结果列表 String targetNode = stack.pop(); resultList.add(targetNode); // 找到当前节点所能到达的节点并入栈 for(Route route : graph.getRotes()){ if(!route.getFrom().equals(targetNode)) continue; // 已加入栈或写入结果列表的节点表示已搜索过，跳过 if(resultList.contains(route.getTo()) || stack.contains(route.getTo())) continue; stack.push(route.getTo()); } } return resultList; }

执行后发现结果和之前不太一样，这是由于栈的先进后出原则，导致先找到的目标节点最后才进行搜索。如果想与之前结果一致，则可以再用一个栈缓存找到的节点，等找到所有的路径搜索完成后再将缓存栈中的节点以此加入元数据栈。

/** * 深度优先遍历（栈） * @param node 起始节点 * @param graph 目标图结构 * @return 遍历结果的节点顺序列表 */ public List DFS(String node, Graph graph){ List resultList = new ArrayList(); // 构建栈，加入起始节点 Stack stack = new Stack(); stack.add(node); while(!stack.isEmpty()){ // 将栈顶节点出栈并加入搜索结果列表 String targetNode = stack.pop(); resultList.add(targetNode); // 找到当前节点所能到达的节点并入栈 Stack tmpStack = new Stack(); for(Route route : graph.getRotes()){ if(!route.getFrom().equals(targetNode)) continue; // 已加入栈或写入结果列表的节点表示已搜索过，跳过 if(resultList.contains(route.getTo()) || stack.contains(route.getTo())) continue; tmpStack.push(route.getTo()); } while(!tmpStack.isEmpty()){ stack.push(tmpStack.pop()); } } return resultList; }

【本文地址】

图的深度优先遍历DFS(JAVA)

图的深度优先遍历DFS(JAVA)

今日新闻

推荐新闻